package A一周刷爆LeetCode.A基础班.F二叉树;

/**
 * @author wei.zhao
 * @description: 是否是平衡二叉树
 * @date 2022年02月24日 17:09
 */
public class Code09_IsBBT {

    public static void main(String[] args) {
        Node head = new Node(7);
        head.left = new Node(5);
        head.right = new Node(9);
        head.left.left = new Node(4);
        head.left.right = new Node(6);
        head.right.left = new Node(8);
        head.right.right = new Node(10);
        head.left.left.left = new Node(11);
        head.left.left.left.left = new Node(12);
        System.out.println("是否是平衡二叉树：" + isBBT(head));
    }

    private static boolean isBBT(Node head) {
        Info info = process(head);
        return info.isB;
    }

    private static Info process(Node node) {
        if (node == null) {
            return new Info(true, 0);
        }
        Info left = process(node.left);
        Info right = process(node.right);
        boolean isB = left.isB && right.isB && Math.abs(left.level - right.level) < 2;
        int level = Math.max(left.level, right.level) + 1;
        return new Info(isB, level);
    }

    public static class Info {
        public boolean isB;
        public Integer level;

        public Info(boolean isB, Integer level) {
            this.isB = isB;
            this.level = level;
        }
    }

}
